package arithmetic.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author jiangfeng on 2022/3/4
 */
public class QuickSort4 {

    public static void main(String[] args) {

        int[] arrTest = {3,6,2,3,7,9,8,5};
        //
        quickSort(arrTest,0,arrTest.length-1);
        System.out.println(Arrays.toString(arrTest));

        int size = 20;
        int[] arr = new int[size];
        Random r = new Random(1);
        for (int i = 0; i < size; i++) {
            arr[i] = r.nextInt(1000);
        }

        System.out.println(Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[] a,int l,int r){
        if(l>=r){
          return;
        }
        int patison = l;
        for (int i = l; i <= r; i++) {
            // 以最右的值为基准值,
            // 比基准值小,两个指针都+1,并且换位置.
            if(a[i]<a[r]){
                swap(a,patison++,i);
            }
        }
        swap(a,r,patison);
        //二分法
        quickSort(a,l,patison-1);
        quickSort(a,patison+1,r);
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
